// https://leetcode.cn/problems/word-search/submissions/

struct Node{
    int x;
    int y;
};
class Solution {
public:
    vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    bool isBounded(int x, int y, vector<vector<char>> &board) {
        int n = board.size();
        int m = board[0].size();
        return x >= 0 && x < n && y >= 0 && y < m;
    }
    bool dfs(vector<vector<char>>& board, string word, int idx, int x, int y, vector<vector<bool>>& visited) {
        if (idx == word.length()) return true;
        if (!isBounded(x, y, board)) return false;
        if (visited[x][y] || board[x][y] != word[idx]) return false;
        visited[x][y] = true;
        for (int i = 0; i < 4; ++i) {
            if (dfs(board, word, idx + 1, x + dir[i][0], y + dir[i][1], visited))
            return true;
        }
        visited[x][y]= false; //注意
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty()) {
            return word == "";
        }
        int n = board.size();
        int m = board[0].size();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                vector<vector<bool>> visited(n, vector<bool>(m, false));
                if (dfs(board, word, 0, i, j, visited)) return true;
            }
        }
        return false;
    }
};